package leet;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 76. Minimum Window Substring
 * 
 * 
 * Given a string S and a string T, find the minimum window in S which will
 * contain all the characters in T in complexity O(n).
 * 
 * Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
 * 
 * @author zhujunbing
 * @date 2019年4月24日
 */
public class Leet0076 {

	public static void main(String[] args) {
		Leet0076 leet = new Leet0076();

		// String s = "ADOBECODEBANCACEEEE";
		// String t = "ABC";
		// String s = "ab";
		// String t = "a";
		String s = "cabdcbad";
		String t = "cda";
		String min = leet.minWindow(s, t);
		System.out.println(min);

	}

	/**
	 * 常规做法，
	 * 
	 * <pre>
	 * 数组记录t中char出现数量以及包含的char种类个数
	 * start,end=0
	 * 1）先移动end，用数组记录char出现数量，并记录数量满足的种类，
	 * 2）当种类符合t中种类时，移动start至不能移动为止，记录min(end-start) end，start
	 * 重复1，2至end移动到尾端
	 * </pre>
	 * 
	 * @param s
	 * @param t
	 * @return
	 * @date 2019年4月24日
	 */
	public String minWindow(String s, String t) {

		int[] tcount = new int[128];

		char[] tArr = t.toCharArray();

		for (char c : tArr) {
			tcount[c]++;
		}

		int need = 0;

		for (int count : tcount) {
			if (count > 0) {
				need++;
			}
		}

		int[] scount = new int[128];

		int length = -1;
		int l = 0;
		int r = 0;

		int start = 0;
		int end = 0;

		//

		int count = 0;

		// 移动end
		while (end < s.length()) {
			char c = s.charAt(end);

			if (tcount[c] > 0 && ++scount[c] == tcount[c]) {
				count++;
			}

			// 包含情况下，移动start
			while (count == need) {
				char cc = s.charAt(start);

				if (length == -1 || end - start < length) {
					length = end - start;
					l = start;
					r = end;
				}

				if (tcount[cc] > 0 && --scount[cc] < tcount[cc]) {
					count--;
				}
				start++;
			}

			end++;
		}
		return length == -1 ? "" : s.substring(l, r + 1);
	}

}
